package MaxSumofRectangleNoLargerThanK;

import java.util.TreeSet;

public class Solution {
	    public int maxSumSubmatrix(int[][] matrix, int k) {
	        if(matrix.length == 0) return 0;
	        int m = matrix.length, n = matrix[0].length;
	        int result=0;
	        for (int start=0;start<n;start++){
	        	int[] sums = new int[m];
	        	for (int end=start;end<n;end++){
	        		for (int i=0;i<m;i++)
	        			sums[i]=sums[i]+matrix[i][end];
	        		TreeSet<Integer> set=new TreeSet<>();
	        		set.add(0);
	        		int current=0;
	        		for (int sum:sums){
	        			current=current+sum;
	        			Integer t=set.ceiling(current-k);
	        			if (t!=null) result=Math.max(result, current-t);
	        			set.add(current);
	        		}
	        	}
	        }
	        return result;
	    }
	   
}

/*题目大义：给定矩阵,求矩形覆盖内数字之和最接近且不超过K(k-sum最小)
1.降维,sums[i]表示矩阵[i][x->n]之和
2.枚举行(列)起点，计算sums[i]
3.Treeset处理答案 讲前sums[i]存入set中,需要找到k-(current-t)最小且大于0
等价于找到set中出现的大于current-k的最小元素t*/


